Embodiments of the present invention relate to software arrays, and more specifically to dynamic atomic arrays that are non-blocking, wait-free, resizable, and thread-safe.
Dynamic arrays are very useful data structures that are used extensively in software. A dynamic array is an array that can be resized and allows for elements of the array to be added or removed. The elements of the array can be of any available data type. For example, most modern programming languages that follow object oriented methodologies provide for dynamic arrays whose elements can be integers or floating point numbers. In addition, dynamic reference arrays are available wherein the array elements are not of a primitive data type, but rather the elements themselves are more complex types as can be represented by an object instantiated from a class definition.
Dynamic arrays can grow or shrink in size as needed by the software program that is utilizing the dynamic array. In many cases, the number of array elements that will be needed is not known in advance. The dynamic array allows the software developer to grow or shrink the size of the array as required, thus providing for more efficient use of system resources, such as memory. As array elements are added or removed, memory can be allocated or released, thus ensuring that the dynamic array is only using the amount of memory that is optimal for the current size of the array.
As computing hardware and software have evolved, the use of multi-threaded programs running on multi-core processors has become more commonplace. Standard computers for home use today typically contain between 2 to 4 processing cores. More advanced machines may contain multiple processors, each of which containing multiple cores. Software has been evolving to take advantage of the multi-processor hardware. For example, most modern programming languages support multi-threaded programs, which allow for a single processor to execute two or more tasks, or threads, of a single process in what appears to be concurrent operation. With the widespread availability of multi-cored processors, threads may not only appear to execute concurrently, but are in fact executing concurrently, each thread executing within a different core of the processor.
A standard dynamic array is ill suited to operation within a multi-threaded process. In common parlance, the dynamic array may be said to be thread unsafe. For example, it is possible that one thread may be attempting to expand the size of the array, while at the same time a second thread is attempting to decrease the size of the array. Such conflicts can easily lead to corruption of the dynamic array structure, and must be avoided. The avoidance of such conflicts is sometimes achieved by the use of read/write locks on the dynamic array. A thread wishing to access the dynamic array may acquire a lock on the array while the thread operates on the array. Other threads that wish to access the array must wait, or block, until the locking thread has released the lock.
Such a solution is not optimal for a number of reasons. One reason is that there is processing overhead required for a thread to acquire a lock on a dynamic array, and then release the lock once processing is complete. Although each individual lock and unlock operation is individually inconsequential, when aggregated over multiple threads, and for each and every access of the dynamic array, the locking and unlocking overhead can become significant. Furthermore, the use of locks for concurrent access to dynamic arrays is problematic because once a thread has locked the dynamic array, all other threads are blocked from accessing that dynamic array until the lock is released. It is possible that a higher priority thread may be blocked because it is waiting for access to the dynamic array, but the dynamic array is currently locked by a lower priority thread. Such a situation is referred to as priority inversion and is not desired.
Many modern programming languages provide for thread-safe versions of non-dynamic arrays. For example, the Java™ programming language provides atomic arrays for a variety of data types, including integers, longs, floats, doubles, and reference arrays. In concurrent programming, such as multi-threaded programming, an atomic operation refers to a set of operations that can be combined so that they appear to the rest of the system to be a single operation with only two possible outcomes: success or failure. Any changes made by an atomic operation will not be visible to the remainder of the system until all of the operations of the set of operations completes. In addition, if any of the operations within the set of operations fails, the entire atomic operation fails, and the system reverts to the state it was in prior to the start of the atomic operation. An atomic array allows for multiple threads to concurrently access the atomic array, without requiring the use of locks. For example, if one thread is altering the value of an array element, such a change will not be visible to other threads until the operation has completed. However, atomic arrays are not dynamic, meaning that the array cannot grow or shrink as required by the process using the atomic array. The techniques used for implementing dynamic arrays are generally not applicable to atomic arrays, because those techniques are not thread-safe and are generally wasteful of computing resources.
Embodiments of the present invention provide for thread-safe, non-blocking, wait-free dynamic atomic arrays.